<?php
class SplayTree extends BinarySearchTree
{
    /**
     * @var BinaryNode $root
     * @var BinaryNode $nullNode
     * @var BinaryNode $header
     * @var BinaryNode $newNode
     */
    public $root=null;
    protected $nullNode=null;
    protected $header=null;
    protected $newNode=null;
    public function __construct()
    {
        $this->nullNode = new BinaryNode();
        $this->nullNode->left = $this->nullNode->right = $this->nullNode;
        $this->header = new BinaryNode();
    }
    /**
     * 从上到下展开
     * @param mixed $x 展开的目标节点
     * @param BinaryNode $t 要展开的子树的根节点
     * @return 
     */
    public function splay($x,$t)
    {
        /**
         * $header的左节点就是R树的根，右节点就是L树的根，这个地方跟普通的二叉查找树相反，这是碎片产生的顺序决定的
         * $left_tree_max是L树上最大的节点
         * $right_tree_min是R树上最小的节点
         * 开始时这三个树相同
         * @var BinaryNode $left_tree_max
         * @var BinaryNode $right_tree_min
         */
        $this->header->left = $this->header->right = $this->nullNode;
        $left_tree_max = $right_tree_min = $this->header;
        $this->nullNode->data = $x;
        while(1){
            if($x < $t->data){
                if($t->left == null){
                    break;
                }
                elseif($x < $t->left->data){
                    //顺时针旋转
                    $left=$t->left;
                    $t->left=$left->right;
                    $left->right=$t;
                    $t = $left;
                }
                if($t->left !==null){
                    $right_tree_min->left=$t;
                    $right_tree_min=$t;
                    $t=$t->left;
                    $right_tree_min->left=null;
                }
            }
            elseif($x > $t->data){
                if($t->right === null){
                    break;
                }
                elseif($x > $t->right->data){
                    //逆时针旋转
                    $right=$t->right;
                    $t->right=$right->left;
                    $right->left=$t;
                    $t=$right;
                }
                if($t->right){
                    $left_tree_max->right=$t;
                    $left_tree_max=$t;
                    $t=$t->right;
                }
            }
            else{
                break;
            }
        }
        $left_tree_max->right=$t->left;
        $right_tree_min->left=$t->right;
        $t->left=$this->header->right;
        $t->right=$this->header->left;
        return $t;
    }
    public function insert($x)
    {
        $newNode=BinaryNode::create($x);
        if($this->root === null){
            $this->root=$newNode;
        }
        else{
            $this->root=$this->splay($x,$this->root);
            if($x < $this->root->data){
                $newNode->left=$this->root->left;
                $newNode->right=$this->root;
                $this->root->left=null;
                $this->root=$newNode;
            }
            elseif($x > $this->root->data){
                $newNode->right=$this->root->right;
                $newNode->left=$this->root;
                $this->root->right=null;
                $this->root=$newNode;
            }
            else{
                return;
            }
        }
    }
    public function remove($x,$node=null)
    {
        /** @var BinaryNode $newTree */
        if(!$this->contains($x)){
            return;
        }
        if($this->root->left == null){
            $newTree=$this->root->right;
        }
        else{
            $newTree=$this->root->left;
            $newTree=$this->splay($x,$newTree);
            $newTree->right=$this->root->right;
        }
        $this->root=$newTree;
    }
    public function contains($x,$node=null)
    {
        $this->root=$this->splay($x,$this->root);
        return $x === $this->root->data;
    }
}
